Powerful video display cards that have recently been developed for use on personal computers and workstations specifically designed for graphics computations are capable of rendering three-dimensional (3D) images on a display in real time. However, in regard to computer games and other applications, it is desirable to enable less powerful personal computers, other specialized computing devices (e.g., video game consoles), and personal computers that do not include such advanced 3D video display cards to render images in real time in response to user input and/or program generated events. For example, it may be desirable to render an image on a display in real time so that the image simulates the refraction that occurs as light passes through a “bumpy” glass layer, or to simulate the appearance of light reflected by a mirror surface into the image, or to map an image onto an arbitrary surface. A simulation of any of these optical effects should show highlights, shading, distortion, tint caused by the color of a glass or mirror, and reflections from the surface.
An initial need for a method that facilitates real-time rendering of an image on a typical personal computer not having the power of a graphics workstation arose in connection with two requirements. In the first requirement, it became necessary to enable a user to select a patch (i.e., a generally rectangular region) in an image applied to a 3D surface, and to enable a user to freely drag the patch over the 3D surface, so that the patch always appears to remain on the surface in the rendered image. This feature should be accomplished while maintaining an acceptable image quality and should achieve real-time performance. In the second requirement, it became necessary to simulate the appearance of an image distorted by light passing through a lump of glass as objects are moved behind the glass (relative to the viewer's position) by a user manipulating a mouse or other pointing device. Related problems requiring a solution include the use of a distorting mirror to modify the appearance of objects appearing in an image. It was recognized that any solution to these problems should also be able to handle combinations of these optical rendering problems.
A technique that addresses the problems noted above should be capable of simulating other real-time rendering effects. For example, there are many applications in which it would be desirable to simulate the rendering of classic morphing effects. The morphing process portrays the gradual change of an image of one object into an image of a different object. Furthermore, the simulated rendering of images should enable anti-aliasing to be carried out by properly blending the foreground of an object with its background along the edges of the object. While solutions to these problems exist in the prior art, they cannot be readily implemented without the use of a relatively powerful computer or by employing an advanced video graphics adapter. For example, real-time global illumination in an image undergoing changes can readily be achieved by using ray tracing in which the behavior of light rays in a rendered image is simulated by following the reverse path of each ray of light as it travels from a source to the observer. Although ray tracing provides high quality results, it is extremely computationally intensive and therefore, unacceptably slow if attempted on a typical home personal computer.
Certain techniques have been developed in the prior art to address the limitations of less powerful computers in implementing specific aspects of real-time rendering. One solution developed to deal with hidden surfaces when rendering an image is known as “z-buffering.” However, z-buffering does not model global illumination effects, such as reflections, but instead accumulates, for each pixel position in an image, data for an object that is closest to the observer. Indeed, most techniques known in the prior art for rendering an image in real time are either too computationally intensive and thus too slow to implement, or produce artifacts, including incorrect highlights or polygonal silhouettes, leading to unacceptably low-quality rendering, or like the polygon-based 3D rendering approach based upon the z-buffering method, are incomplete solutions to the problem.
An early attempt to solve some of these problems was developed for use in PANDORA'S BOX™, a game created and marketed by Microsoft Corporation. In this game, only some of the problems noted above were solved. Real-time rendering was simulated in the game using a morph map that stores a set of data associated with each pixel position in an image. To avoid delays in rendering an image, the morph maps required in the game were produced in a pre-processing step using conventional rendering techniques. The morph maps thus produced were then included in the game software that was distributed to purchasers of the game. However, the prior art game software included only one set of morph data for each pixel position in a given output image and was incapable of classic morphing, or of implementing anti-aliasing, because it did not employ multiple input images, multiple sets of pixel data for each pixel location, or a blending (alpha) factor. Also, it could not produce colored modulation and highlights and was incapable of simulating full ray tracing functionality.
Accordingly, the prior art approach in this earlier product was simply a subset and was an incomplete solution to the problems noted above. The present invention was developed to address these deficiencies in this prior art.